// 统计所有小于非负整数 n 的质数的数量。
#include<vector>
#include<string>
#include<set>
#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    int countPrimes(int n) {
        bool prime[n+1];
        for(int i=2;i<n;i++){
            prime[i] = true;
        }
        int count =0;
        for(int i=2;i<=n;i++){
            if(prime[i]){
                for(int j=i+i;j<n;j+=i){
                    prime[j] = false;
                }
            }
        }
        for(int i=0;i<=n;i++){
            if(prime[i] == true){
                count++;
            }
        }
        return count;
    }
};